//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_CONTAINER_CINTRUSIVELIST_H_
#define _BUOLA_CONTAINER_CINTRUSIVELIST_H_

#include <buola/buola.h>
#include <buola/container/detail/csizeholder.h>
#include <buola/iterator/facade.h>

namespace buola {

namespace detail {

    template<typename tPointer>
    struct CListNode
    {
        typedef ORebindPointer<tPointer,detail::CListNode<tPointer>> tNodePointer;
        tNodePointer mPrev,mNext;
    };

/*namespace detail*/ }

///\addtogroup container
///@{

/////////////////////////////////////////////////////////////////////////////////////////////////

/// intrusive list

/// Doubly-linked list where the node information is stored in the data object, so that no
/// additional dynamic allocation is needed
///
/// \tparam tType The type of the objects the list will contain. Must inherit from SHook
/// \tparam tPointer The pointer type to use
///
/////////////////////////////////////////////////////////////////////////////////////////////////

template<typename tType,typename tPointer=tType*>
class CIntrusiveList : public UUncopiable
{
    typedef detail::CListNode<tPointer> tNode;
    typedef typename tNode::tNodePointer tNodePointer;
    
public:
    typedef tPointer pointer;
    typedef ORebindPointer<tPointer,const tType> const_pointer;

    typedef tType value_type;
    typedef tType& reference;
    typedef const tType& const_reference;
    typedef std::ptrdiff_t difference_type;
    typedef std::size_t size_type;

    ///CIntrusiveList hook
    struct SHook : private tNode
    {
        friend tType &get_list_item_from_node(tNode &pNode)      {   return static_cast<tType&>(pNode);  }
        friend tNode &get_list_node_from_item(tType &pNode)      {   return pNode;  }
    };

private:
    ///CIntrusiveList iterator
    template<bool vConst>
    class SIterator : public IFacade<SIterator<vConst>,std::bidirectional_iterator_tag,
                                     typename std::conditional<vConst,const tType,tType>::type>
    {
        typedef typename std::conditional<vConst,const_reference,reference>::type TReference;

    public:
        ///default constructor

        ///leaves the iterator in a non-deferenceable, non-incrementable, non-comparable state
        SIterator()
            :   mNode(nullptr)
        {}

        ///initializes the iterator from a non const iterator
        SIterator(const SIterator<false> &pNonConstIt)
            :   mNode(pNonConstIt.mNode)
        {}

    private:
        ///initializes the iterator from a \c pNode
        SIterator(tNodePointer pNode)
            :   mNode(pNode)
        {}

        ///returns the item the iterator points to
        TReference Dereference() const
        {
            return get_list_item_from_node(*mNode);
        }

        ///makes the iterator point to the next object in the list
        void Increment()
        {
            mNode=mNode->mNext;
        }

        ///makes the iterator point to the previous object in the list
        void Decrement()
        {
            mNode=mNode->mPrev;
        }

        ///returns true if the two iterators point to the same node, or they are both end iterators for the same list
        bool Equal(const SIterator &pO) const
        {
            return mNode==pO.mNode;
        }

        tNodePointer mNode;

        template<bool>
        friend class SIterator;
        friend class CIntrusiveList;
        friend class IFacade<SIterator<vConst>,std::bidirectional_iterator_tag,
                             typename std::conditional<vConst,const tType,tType>::type>;
    };

    template<bool>
    friend class SIterator;

public:
     typedef SIterator<false> iterator;
     typedef SIterator<true> const_iterator;
     typedef std::reverse_iterator<iterator> reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    ///constructs an empty list

    ///\throws nothing
    CIntrusiveList()
    {
        mRoot.mPrev=&mRoot;
        mRoot.mNext=&mRoot;
    }

    ///constructs an empty list and inserts elements from [\p pB, \p pE) into it

    ///\pre Dereferencing iterator must yield an lvalue of type value_type
    ///\pre The elements must not be in any list
    ///
    ///\post The elements are in the list
    ///
    ///\complexity Linear in the number of elements to insert
    ///
    ///\throws nothing
    template<typename tIt>
    CIntrusiveList(tIt pB,tIt pE)
    {
        mRoot.mPrev=&mRoot;
        mRoot.mNext=&mRoot;

        insert(begin(),pB,pE);
    }
    
    ///move constructor
    CIntrusiveList(CIntrusiveList &&pRH)
    {
        if(pRH.mRoot.mPrev==&pRH.mRoot)
        {
            mRoot.mPrev=&mRoot;
            mRoot.mNext=&mRoot;
        }
        else
        {
            mRoot=pRH.mRoot;
            mRoot->mNext->mPrev=&mRoot;
            mRoot->mPrev->mNext=&mRoot;
        }
    }

    ///destructor

    ///Doesn't delete the objects in the tree, i.e. no destructor is called
    ///
    ///\post the elements previously in the list are not in any list
    ~CIntrusiveList()
    {}

    ///returns an \c iterator pointing to the beginning of the list
    iterator begin()
    {
        return iterator(mRoot.mNext);
    }

    ///returns a \c const_iterator pointing to the beginning of the list
    const_iterator begin() const
    {
        return cbegin();
    }

    ///returns a \c const_iterator pointing to the beginning of the list
    const_iterator cbegin() const
    {
        return const_iterator(mRoot.mNext);
    }

    ///returns an \c iterator pointing to the end of the list
    iterator end()
    {
        return iterator(&mRoot);
    }

    ///returns a \c const_iterator pointing to the end of the list
    const_iterator end() const
    {
        return cend();
    }

    ///returns a \c const_iterator pointing to the end of the list
    const_iterator cend() const
    {
        return const_iterator(const_cast<tNode*>(&mRoot));
    }

    ///returns a \c reverse_iterator pointing to the end of the list
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    ///returns a \c const_reverse_iterator pointing to the end of the list
    const_reverse_iterator rbegin() const
    {
        return reverse_iterator(end());
    }

    ///returns a \c const_reverse_iterator pointing to the end of the list
    const_reverse_iterator crbegin()
    {
        return const_reverse_iterator(end());
    }

    ///returns a \c reverse_iterator pointing to the beginning of the list
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    ///returns a \c const_reverse_iterator pointing to the beginning of the list
    const_reverse_iterator rend() const
    {
        return reverse_iterator(begin());
    }

    ///returns a \c const_reverse_iterator pointing to the beginning of the list
    const_reverse_iterator crend()
    {
        return const_reverse_iterator(begin());
    }

    ///returns \c true if the container is empty

    ///\complexity constant
    bool empty() const
    {
        return mRoot.mNext==&mRoot;
    }

    ///returns the number of elements stored in the tree

    ///\complexity linear with the number of elements in the list
    size_type size() const
    {
        return std::distance(begin(),end());
    }

    ///returns a reference to the first element in the list
    reference front()
    {
        return *begin();
    }
    
    ///returns a const reference to the first element in the list
    const_reference front() const
    {
        return *cbegin();
    }

    ///returns a reference to the last element in the list
    reference back()
    {
        return *rbegin();
    }

    ///returns a const reference to the last element in the list
    const_reference back() const
    {
        return *crbegin();
    }

    ///appends an element to the beginning of the list

    ///\pre the element is not in any list
    void push_front(reference pElement)
    {
        insert(begin(),pElement);
    }

    ///appends an element to the end of the list

    ///\pre the element is not in any list
    void push_back(reference pElement)
    {
        insert(end(),pElement);
    }
    
    ///moves an element to the beginning of the list

    ///\pre the element is in some list (it can be the same one)
    void MoveFront(reference pElement)
    {
        erase(pElement);
        insert(begin(),pElement);
    }

    ///moves an element to the end of the list

    ///\pre the element is in some list (it can be the same one)
    void MoveBack(reference pElement)
    {
        erase(pElement);
        insert(end(),pElement);
    }

    ///moves all elements in \p pOther to the beginning of this list
    void MoveFront(CIntrusiveList &pOther)
    {
        if(pOther.empty()) return;

        pOther.mRoot.mPrev->mNext=mRoot.mNext;
        mRoot.mNext->mPrev=pOther.mRoot.mPrev;
        pOther.mRoot.mNext->mPrev=&mRoot;
        mRoot.mNext=pOther.mRoot.mNext;

        pOther.clear();
    }
    
    ///moves all elements in \p pOther to the end of this list
    void MoveBack(CIntrusiveList &pOther)
    {
        if(pOther.empty()) return;

        pOther.mRoot.mNext->mPrev=mRoot.mPrev;
        mRoot.mPrev->mNext=pOther.mRoot.mNext;
        pOther.mRoot.mPrev->mNext=&mRoot;
        mRoot.mPrev=pOther.mRoot.mPrev;

        pOther.clear();
    }

    ///inserts \p pValue into the list

    ///\pre the element is not in any list
    iterator insert(iterator pPos,reference pValue)
    {
        tNode &lNode=get_list_node_from_item(pValue);
        lNode.mNext=pPos.mNode;
        lNode.mPrev=pPos.mNode->mPrev;
        pPos.mNode->mPrev=&lNode;
        lNode.mPrev->mNext=&lNode;
        return iterator(&lNode);
    }

    ///inserts the elements in the range [\p pB, \p pE) into the list

    ///\pre the elements are not in any list
    template<typename tIt>
    void insert(iterator pPos,tIt pB,tIt pE)
    {
        while(pB!=pE)
        {
            pPos=insert(pPos,*(pB++));
            ++pPos;
        }
    }

    ///erases the element pointed to by the iterator \p pI
    iterator erase(iterator pI)
    {
        pI.mNode->mPrev->mNext=pI.mNode->mNext;
        pI.mNode->mNext->mPrev=pI.mNode->mPrev;
        return iterator(pI.mNode->mNext);
    }

    ///erases the element range [\p pB, \p pE)
    iterator erase(const_iterator pB, const_iterator pE)
    {
        if(pB!=pE)
        {
            pB.mNode->mPrev->mNext=pE.mNode;
            pE.mNode->mPrev=pB.mNode->mPrev;
        }
        return pE;
    }

    ///erases the element \p pValue

    ///\pre the element must be in some list
    ///
    ///The function is static since elements can be erased from a list without knowing which list they are in
    static void erase(reference pValue)
    {
        tNode &lNode=get_list_node_from_item(pValue);

        lNode.mPrev->mNext=lNode.mNext;
        lNode.mNext->mPrev=lNode.mPrev;
    }
    
    ///erases all elements
    void clear()
    {
        mRoot.mPrev=&mRoot;
        mRoot.mNext=&mRoot;
    }

    ///returns an iterator to the element

    ///\pre the element is in some list
    static iterator IteratorTo(reference pValue)
    {
        return iterator(&pValue);
    }

    ///returns a const_iterator to the element

    ///\pre the element is in some list
    static const_iterator IteratorTo(const_reference pValue)
    {
        return const_iterator(&pValue);
    }

private:
    tNode mRoot;
};

///@}

/*namespace buola*/ }

#endif
